Section: Software

Grph

Participants : David Coudert, Luc Hogie [correspondant] , Aurélien Lancin, Grégory Morel, Issam Tahiri.

Around 20,000 lines of code, developed in Java.

The objective of Grph is to provide researchers and engineers a suitable graph library for graph algorithms experimentation and network simulation. Grph is primarily a software library, but it also comes with a set of executable files for user interaction and graph format conversion; as such, it can be used autonomously. Performance and accessibility are the primary targets of the Grph library. It allows manipulating large graphs (millions of nodes). Its model considers mixed graphs composed of directed and undirected simple- and hyper-edges. Grph comes with a collection of base graph algorithms which are regularly augmented.

So far, known users of the Grph library include people at Mascotte and others involved in the FP7 EULER project. It got some contribution from the Inria team GANG who contributed Grph with an implementation of the four-sweep algorithm which provides accurate lower bound on the diameter in linear time. It has a number of other academic users including research students at Bergamo University (Italy), and University of Southern Denmark (students supervised by Jørgen Bang-Jensen).

Grph includes bridges to other graph libraries such as JUNG, JGraphT, CORESE (a software developed by the WIMMICS team Inria-I3S), LAD (Christine Solnon, LIRIS), Nauty (Brendan D. McKay), as well as specific algorithms developed by Matthieu Latapy and Jean-Lou Guillaume (LIP6), etc.

Grph is distributed under the terms of a license defined by its contributors and is available for download. This license allows free usage and access to the source code. See http://www-sop.inria.fr/mascotte/software/grph .

In 2012, numerous graph algorithms have been added to Grph , such as maximum matching, minimum vertex cover (brute force, branching, Niedermeier), maximum independent set (Fomin/Grandoni/Kratsch). Furthermore, to answer a number of issues about the generation of graph instances with particular properties, a framework for evolutionary computing dedicated to graphs was integrated to Grph . Moreover, a reworked version of Mascsim was integrated in Grph .

On-going works concern the distributed execution of graph algorithms, and a bridge to Sage.

See also the web page http://www-sop.inria.fr/mascotte/software/grph/ .